package algorithm.color2w.algorithm.linkedlist;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author wjl <br/>
 * @version 1.0
 * @ClassName: PrintReverseLinkedList <br/>
 * @Description: 从尾到头反过来打印出每个结点的值。<br />
 * @date: 2020/1/2 10:10<br/>
 */
public class PrintReverseLinkedList {

    public static class ListNode {
         int val;
         ListNode next = null;

         ListNode(int val) {
             this.val = val;
         }
     }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        System.out.println("-- "+printListFromTailToHead3(node1));
    }

    /*方法一：递归，如果是最后一个节点，返回一个带有该节点值的列表
           否则，执行递归，并将方法返回的列表和当前节点的值add到新的列表中，进行返回
           时间& O(N)  空间& O(nLog(n))
    */
    public static ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        ArrayList<Integer> arrList = new ArrayList<>();
        if (listNode.next == null){
            arrList = new ArrayList<>();
            arrList.add(listNode.val);
            return arrList;
        }else {
            arrList.addAll(printListFromTailToHead1(listNode.next));
            arrList.add(listNode.val);
            return arrList;
        }
    }

    /*方法二：头插法，获取逆序的列表
           时间& O(N)  空间& O(nLog(n))
    */
    public static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ListNode head= new ListNode(0);
        while (listNode != null){
            ListNode memo = listNode.next;
            listNode.next = head.next;
            head.next = listNode;
            listNode = memo;
        }
        ArrayList<Integer> result = new ArrayList<>();
        head = head.next;
        while(head != null){
            result.add(head.val);
            head = head.next;
        }
        return result;
    }

    /*方法三：栈，将值放入栈中，然后再读出来
       时间& O(N)  空间& O(nLog(n))
*/
    public static ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        Stack<Integer> listStack = new Stack<>();
        while (listNode != null){
            listStack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> result = new ArrayList<>();

        while(!listStack.isEmpty()){
            result.add(listStack.pop());
        }
        return result;
    }
}
